﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶元素下一个位置的下标
	int capacity;//容量
}ST;

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

void STPush(ST* pst, STDataType x)
{
	assert(pst);

	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	//真正入栈
	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);//确保里面有数据
	pst->top--;
}

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);//确保里面有数据

	return pst->a[pst->top - 1];
}

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//返回一个判断值
}


void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

void Conversion(ST* pst, int n)
{
	if (n == 0)
	{
		printf("0x0\n");
		return;
	}
	while (n)
	{
		int count = n % 16;
		// 入栈
		STPush(pst, count);
		n /= 16;
	}
	char has[17] = "0123456789ABCDEF";
	printf("0x");
	while (!STEmpty(pst))
	{
		char ans = has[STTop(pst)];
		STPop(pst);
		printf("%c", ans);
	}
	printf("\n");
}

bool Match(ST* pst, const char *str)
{
	for (int i = 0; i < strlen(str); i++)
	{
		if (str[i] == '(')
			STPush(pst, str[i]);
		else if (str[i] == ')')
		{
			if (STEmpty(pst))
				return false;
			else
			{
				if (STTop(pst) != '(')
					return false;
				else
					STPop(pst);
			}
			
		}
	}
	if (!STEmpty(pst))
		return false;
	else
		return true;
}

int GetPriority(char op)
{
	if (op == '*' || op == '/')
		return 2;
	if (op == '+' || op == '-')
		return 1;
	return 0;
}

int ApplyOp(int a, int b, char op)
{
	switch (op)
	{
	case '+': return a + b;
	case '-': return a - b;
	case '*': return a * b;
	case '/':
		if (b == 0)
		{
			printf("Error: 除数不为 0\n");
			exit(1);
		}
		return a / b;
	default:
		return 0;
	}
}

int Evaluate(const char* expr)
{
	ST values;  // 数值栈
	ST ops;     // 运算符栈
	STInit(&values);
	STInit(&ops);

	// 识别数字进栈
	for (int i = 0; i < strlen(expr);)
	{
		if (expr[i] >= '0' && expr[i] <= '9')
		{
			int val = 0;
			while (expr[i] >= '0' && expr[i] <= '9')
			{
				val = val * 10 + (expr[i] - '0');
				i++;
			}
			STPush(&values, val);
		}
		else if (expr[i] == '(')
		{
			STPush(&ops, expr[i]);
			i++;
		}
		else if (expr[i] == ')')
		{
			while (!STEmpty(&ops) && STTop(&ops) != '(')
			{
				int b = STTop(&values); STPop(&values);
				int a = STTop(&values); STPop(&values);
				char op = (char)STTop(&ops); STPop(&ops);
				STPush(&values, ApplyOp(a, b, op));
			}
			STPop(&ops);
			i++;
		}
		else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/')
		{
			while (!STEmpty(&ops) && GetPriority(STTop(&ops)) >= GetPriority(expr[i]))
			{
				int b = STTop(&values); STPop(&values);
				int a = STTop(&values); STPop(&values);
				char op = (char)STTop(&ops); STPop(&ops);
				STPush(&values, ApplyOp(a, b, op));
			}
			STPush(&ops, expr[i]);
			i++;
		}
	}

	while (!STEmpty(&ops))
	{
		int b = STTop(&values); STPop(&values);
		int a = STTop(&values); STPop(&values);
		char op = (char)STTop(&ops); STPop(&ops);
		STPush(&values, ApplyOp(a, b, op));
	}

	int result = STTop(&values);
	STDestroy(&values);
	STDestroy(&ops);
	return result;
	
}

//int main()
//{
//	ST st1;
//	STInit(&st1);
//	Conversion(&st1, 163);
//	STDestroy(&st1);
//
//	ST st2;
//	STInit(&st2);
//	const char* que1 = "a+(c-(b-1)+(c-d)*6)";
//	if (Match(&st2, que1))
//		printf("括号匹配\n");
//	else
//		printf("括号不匹配\n");
//	STDestroy(&st2);
//
//	ST st3;
//	STInit(&st3);
//	const char* que2 = "a+(c-(b-1)+(c-d*6)";
//	if (Match(&st2, que2))
//		printf("括号匹配\n");
//	else
//		printf("括号不匹配\n");
//	STDestroy(&st3);
//
//	const char* que3 = "10+(10-(10-1)+(10-10)*6)";
//	int ans = Evaluate(que3);
//	printf("%d\n", ans);
//	return 0;
//}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>

// 引入之前定义的函数
// 若分文件编译，请包含你的 stack.h 或将函数声明提前

//int main()
//{
//	ST s;
//	printf("\n===== 一、十进制转十六进制测试 =====\n");
//	STInit(&s);
//	int nums[] = { 0, 15, 16, 163, 255, 4095, 65535 };
//	for (int i = 0; i < 7; i++)
//	{
//		printf("输入 %d 的十六进制为：", nums[i]);
//		Conversion(&s, nums[i]);
//	}
//	STDestroy(&s);
//
//	printf("\n===== 二、括号匹配测试 =====\n");
//
//	// 测试表达式数组
//	const char* tests[] = {
//		"a+(c-(b-1)+(c-d)*6)",
//		"a+(c-(b-1)+(c-d*6)",
//		"(((a+b)*(c+d)))",
//		"(a+b]*c)",
//		"((a+b)*(c+d)",
//		"",
//		"(())()"
//	};
//
//	// 遍历测试
//	for (int i = 0; i < 7; i++)
//	{
//		// 🔹 每次创建一个新的栈对象
//		ST temp;
//		STInit(&temp);
//
//		printf("表达式：%-25s --> %s\n",
//			tests[i],
//			Match(&temp, tests[i]) ? "括号匹配" : "括号不匹配");
//
//		STDestroy(&temp);  // 🔹 匹配结束后销毁栈
//	}
//
//	
//
//	return 0;
//}


int main()
{
	// 测试用例1：标准表达式（含括号）
	char expr1[] = "3+(2*4)-5/(1+1)";
	int result1 = Evaluate(expr1);
	printf("测试用例 1： %s = %d\n", expr1, result1);

	// 测试用例2：复杂的运算（含乘法、除法、括号）
	char expr2[] = "(5+3)*2-8/4";
	int result2 = Evaluate(expr2);
	printf("测试用例 2： %s = %d\n", expr2, result2);

	// 测试用例3：多个运算符，包含负号
	char expr3[] = "(5+3)*2-8/4";
	int result3 = Evaluate(expr3);
	printf("测试用例 3： %s = %d\n", expr3, result3);

	// 测试用例4：除法与除零错误
	char expr4[] = "6/0";  // 除零错误
	int result4 = Evaluate(expr4);  // 应该处理除零错误

	return 0;
}